 1.分治之概述
   
   分治，就是分而治之。
   分治的一般步骤：
   1)、将原问题分解成若干个规模较小的子问题（子问题和原问题的结构一样，只是规模不一样）
   2)、子问题又不断分解成规模更小的子问题，直到不能再分解（直到可以轻易计算出子问题的解）
   3)、利用子问题的解推导出原问题的解
   所以：分治思想非常适合使用递归实现！！
   注意：分治的适用场景中必须要求子问题之间是相互独立的,如果子问题之间不独立则需要使用动态规划实现！！
   分治思想图示
 
 2.案例一
   
   快速排序(Quick Sort)
   什么叫排序？
       排序前：3,1,6,9,2,5,8,4,7
       排序后：1,2,3,4,5,6,7,8,9(升序) 或者 9,8,7,6,5,4,3,2,1(降序)
   1).概述
   快速排序是1960年由查尔斯·安东尼·理查德·霍尔（Charles Antony Richard Hoare，缩写为C. A. R. Hoare）提出，
简称为东尼·霍尔（Tony Hoare）
   2).Quick Sort 分析
   第一步
   从数组中选择一个轴点元素（Pivot element），一般选择0位置元素为轴点元素
   第二步
       利用Pivot将数组分割成2个子序列
	   将小于 Pivot的元素放在Pivot前面（左侧） 将大于 Pivot的元素放在Pivot后面（右侧） 等于Pivot的元素
放哪边都可以(暂定放在左边)
   第三步
       对子数组进行第一步，第二步操作，直到不能再分割(子数组中只有一个元素)   
   Quick Sort的本质：
   不断地将每一个元素都转换成轴点元素！！
   3).Quick Sort实现思路
   begin指针会不会大于end?
   begin最终会等于end!!
   只要begin==end说明这次的轴点元素已经选择成功！！
   4).代码实现
package com.lg.sort;

import com.lg.utils.IntegerTools;

/**
 * 实现快速排序
 */
public class QuickSort {
    public static void main(String[] args) {
        new QuickSort().sort(IntegerTools.random(10000, 0, 1000));
    }
    //定义数组属性
    private Integer[] arr;

    //接收数组进行排序
    public void sort(Integer[] array) {
        arr = array;
        //打印排序前的数组
        System.out.println("数组排序前：");
        for (int i = 0; i < 20; i++) {
            System.out.print(arr[i] + "_");
        }
        //统计排序花费时间
        final long begin = System.currentTimeMillis();

        //调用自定义的快速排序
        sort(0, arr.length);
        final long end = System.currentTimeMillis();
        System.out.println();
        System.out.println("自定义快速排序花费时间" + (end - begin)/1000.0 + "秒");
        //验证数组是否有序
        System.out.println("数组排序后：");
        for (int i = 0; i < 20; i++) {
            System.out.print(arr[i] + "_");
        }
    }

    /**
     * 接收[开始索引，结束索引]，数组最后一个元素arr.length-1
     *
     * @param end: 是最后索引+1
     * @param
     */
    private void sort(int begin, int end) {
        //对于递归的边界,只有一个元素则跳出
        if (end - begin < 2) {
            return;
        }
        //找到轴点元素的索引位置
        int pivotIndex = getPivotIndex(begin, end);
        //重复一 二步的操作
        //对左边进行快速排序
        sort(begin, pivotIndex); //左闭右开
        //对右边进行快速排序
        sort(pivotIndex + 1, end);

    }

    /**
     * 返回的是轴点元素确定后的索引位置的信息
     *
     * @param begin：开始索引
     * @param end：结束索引
     * @return
     */
    private int getPivotIndex(int begin, int end) {
        //获取0索引位置元素，作为轴点元素，备份
        int pivot = arr[begin];
        //end--,指向最后一个元素
        end--;

        while (begin < end) {
            //第一种情况：拿右边的元素与轴点元素比较
            //比较轴点元素与end指针对应元素的大小关系
            while (begin < end) {
                if (myCompare(pivot, arr[end]) < 0) {
                    //说明轴点元素小于end指针元素
                    end--;
                } else {
                    //end指针元素的值小于等于轴点元素，放在轴的左边
                    arr[begin] = arr[end];
                    begin++;
                    //开始换方向
                    break;
                }
            }

            //第二种情况：拿左边的元素与轴点元素的比较
            //比较轴点元素与begin指针对应元素的大小关系
            while (begin < end) {
                if (myCompare(pivot, arr[begin]) > 0) {
                    //说明轴点元素大于begin指针元素
                    begin++;
                } else {
                    //begin指针元素的值大于等于轴点元素，放在轴的左边
                    arr[end] = arr[begin];
                    end--;
                    //开始换方向
                    break;
                }

            }
        }
        // 把轴点元素赋值给确定的轴点索引位置上
        arr[begin]=pivot;
        //轴点元素索引位置已经确定了
        return begin;
    }

    //比较两个元素的大小

    /**
     * return 0:代表两个元素相等
     * return 1 大于0，代表的是t1>t2
     * return -1 小于0，代表的是t1<t2
     *
     * @param t1
     * @param t2
     * @return
     */
    public int myCompare(Integer t1, Integer t2) {
        return t1.compareTo(t2);
    }
}
   
   生成数组工具类
package com.lg.utils;

public class IntegerTools {
    public static Integer[] random(int count, int min, int max) {
        if (count <= 0 || min > max) return null;
        Integer[] array = new Integer[count];
        int delta = max - min + 1;
        for (int i = 0; i < count; i++) {
            array[i] = min + (int) (Math.random() * delta);
        }
        return array;
    }
}

   5).Quick Sort复杂度以及稳定性分析
   常见递推式与复杂度
   时间递推式                   复杂度
   T(n) = T (n/2) + O(1)        O(logn)
   T(n) = T (n-1) + O(1)        O(n)
   T(n) = T (n/2) + O(n)        O(n)
   T(n) = 2*T (n/2) + O(1)      O(n)
   T(n) = 2*T (n/2) + O(n)      O(nlogn)
   T(n) = T (n-1) + O(n)        O(n^2)
   T(n) = 2*T (n-1) + O(1)      O(2^n)
   T(n) = 2*T (n-1) + O(n)      O(2^n)
   
   时间复杂度
       最坏情况：T(n)=T(n-1) +O(n) = O(n^2)
	   最好情况：T(n)=2 * T(n/2) + O(n) = O(nlogn)
   空间复杂度
       由于递归调用，每次类似折半效果所以空间复杂度是O(logn)
   
   排序算法的稳定性
   对于排序算法还有一个评价指标就是稳定性！！
   什么是排序算法的稳定性？
   如果相等的2个元素，在排序前后的相对位置保持不变，则该算法是稳定的排序算法！！
   
   举例：
   排序前：5, 1, 2a, 4, 7, 2𝑐
   稳定的排序： 1, 2a, 2b , 4, 5, 7
   不稳定的排序：1, 2b , 2a, 4, 5, 7
   
   对于数值类型的排序而言,算法的稳定性没有意义,但是对于自定义对象的排序,排序算法的稳定性是会影响最终结
果的！！
   元素与轴点元素相等
   上述代码实现中，对于与轴点相等的元素选择了移动到左边而不是原地不动，如果发生元素与轴点元素相等的情况，
选择原地不动会出现什么情况？
   如果按照上述标准，不移动与轴点相等的元素，是有可能把数组分割为不均匀的子数组，进而导致产生最坏的时间复
杂度O(n^2)。
   补充：参考代码中的实现，对于与轴点相等元素进行了移动并不是简单移动到左边而是每次移动后会调换方向，所以
即使所有元素全部相等也可以利用轴点元素将序列分割成 2 个均匀的子序列。
   作业
   如何降低快速排序排序最坏时间复杂度产生的概率？